package cn.dglydrpy.study.algorithm.learning.recursive2DP;

import java.util.Stack;

/**
 * 给你一个栈，请你逆序这个栈，
 * 不能申请额外的数据结构，
 * 只能使用递归函数。 如何实现? 
 */
public class Code05_ReverseStackUsingRecursive {

	public static void reverse(Stack<Integer> stack) {
		if (stack.isEmpty()) {
			return;
		}
		
		// 抽掉最下面的元素
		int i = f(stack);
		
		reverse(stack);
		
		// 递归完再push,就在最上面了
		stack.push(i);
	}

	// 栈底元素移除掉
	// 上面的元素盖下来
	// 返回移除掉的栈底元素
	public static int f(Stack<Integer> stack) {
		// 弹出来一个
		int result = stack.pop();
		if (stack.isEmpty()) {
			// 栈底元素
			return result;
		} else {
			// 说明不是栈底元素，递归拿到栈底元素
			int last = f(stack);
			// 恢复栈顶元素
			stack.push(result);
			return last;
		}
	}

	public static void main(String[] args) {
		Stack<Integer> test = new Stack<Integer>();
		test.push(1);
		test.push(2);
		test.push(3);
		test.push(4);
		test.push(5);
		reverse(test);
		while (!test.isEmpty()) {
			System.out.println(test.pop());
		}

	}

}
